package de.dailab.graphworld.pathfinding;

import java.util.ArrayList;

// simple priority queue as a utility for A*
public class PriorityQueue {
	
	private ArrayList<Path> items;
	
	public PriorityQueue(){
		items = new ArrayList<Path>();
	}
	
	public void add(Path path){
		if(items.isEmpty()){
			items.add(path);
		}else{
			boolean added = false;
			int i = 0;
			while(i<items.size()){
				// shorter path found => break, no adding required
				if(items.get(i).equals(path) && items.get(i).compareTo(path)<=0){
					added = true; // no adding neccessary since shorter path exists
					break;
				}
				// longer path found => delete, shorter version already added; since only 1 longer possible => break
				if(items.get(i).equals(path) && items.get(i).compareTo(path)>0){
					items.remove(i);
					i--; // adjust i to deletion of an element
					break;
				}
				// look for spot to add found
				if(!added && items.get(i).compareTo(path)>0){
					items.add(i, path);
					added = true;
				}
				// increase index
				i++;
			}
			// not added yet => add at end
			if(!added)
				items.add(path);
		}
	}
	
	public Path top(){
		return items.get(0);
	}
	
	public Path pop(){
		return items.remove(0);
	}
	
	public boolean isEmpty(){
		return items.isEmpty();
	}

}
